package com.dyz.leetcode;


import java.util.Map;
import java.util.Stack;

public class MaximalRectangle85 {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }

    public int maximalRectangle1(char[][] matrix) {
        if(null==matrix || 0 ==matrix.length || 0==matrix[0].length){
            return 0;
        }
        int ans = 0;
        int R = matrix.length, C = matrix[0].length;
        int [] H = new int [C+1];
        for (int r=0; r<R; R++){
            H[C]=0;
            for (int c=0; c<C;c++){
                if(matrix[r][c]=='0'){H[c]=0;}
                else {++H[c];}
            }
            ans = Math.max(ans,MaxRec(H));
        }
        return ans;


    }

    private int MaxRec(int[] H) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        for(int c=0; c<H.length; c++){
            while (!stack.isEmpty() && H[stack.peek()]>H[c]){
                int h = H[stack.pop()];
                int beg = stack.isEmpty()?-1:stack.peek();
                ans = Math.max(ans, h*(c-beg-1));
            }
            stack.push(c);
        }
        return ans;
    }
}
